package lbj.cyw.dp;
/*
* Offer14-1 剪绳子
*
* 当n>=4时3不可再分,所以dp[3]就等于3,
* 当n<=3时,3和2都需要需要分割,分别返回
* */
public class Offer14cuttingRope1 {
    public int cuttingRope(int n) {
//        if(n==2){
//            return 1;
//        }
//        if(n==3){
//            return 2;
//        }
//        int[] dp=new int[n+1];
//        int[] res=new int[n+1];
//        dp[1]=1;
//        dp[2]=2;
//        dp[3]=3;
//        for(int i=4;i<=n;i++){
//            int max=0;
//            for(int j=1;j<=i/2;j++){
//                dp[i]=Math.max(dp[i],dp[j]*dp[i-j]);
//            }
//            res[i]=dp[i]%1000000007;
//        }
//        return res[n];if(n==2){
        if(n==2){
            return 2;
        }
        if(n==3){
            return 3;
        }
        int res=1;
        while(n>4){
            res*=3;
            n-=3;
        }
        return res*n;
    }
}
